package com.gitee.jsbd.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序 不稳定 （最好：nlogn 最坏：O(n^2)）
 * <p>
 * 快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),
 * 然后对数组进行分区操作,
 * 使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，
 * 如此作为基准的元素调整到排序后的正确位置。
 * 递归快速排序，将其他n-1个元素也调整到排序后的正确位置。
 * 最后每个元素都是在排序后的正确位置，排序完成。
 * 所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
 * </p>
 */
public class QuickSort {


    public static void quickSort(int[] data, int left, int right) {

        int pivotpos = 0;
        if (left < right) {
            pivotpos = partition(data, left, right); // 对数组[left.....right]进行划分
            quickSort(data, left, pivotpos - 1); // 对左区间递归排序
            quickSort(data, pivotpos + 1, right); // 对右区间递归排序
        }

    }

    /**
     * 快速排序的分割函数
     *
     * @param data
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] data, int left, int right) {
        int pivot = data[left];
        while (left < right) {

            while (left < right && data[right] >= pivot) {
                right--;
            }
            if (left < right) {
                data[left] = data[right];
            }

            while (left < right && data[left] <= pivot) {
                left++;
            }
            if (left < right) {
                data[right] = data[left];
            }

            System.out.println(Arrays.toString(data));

        }
        data[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        // 排序前数组
        int[] data = new int[]{5, 8, 7, 9, 1, 2};
        System.out.print("==初始化==：");
        System.out.println(Arrays.toString(data));

        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

}
